#include <map>
#include <unordered_map>
#include <vector>

class Solution {
public:
    int majorityElement(const std::vector<int> &nums) {
        int cur_max = 0;
        int target = nums[0];
        std::unordered_map<int, int> dict;
        for (auto n : nums) {
            if (dict.count(n)) {
                ++dict[n];
                if (dict[n] > cur_max) {
                    cur_max = dict[n];
                    target = n;
                }
            } else {
                dict.insert({n, 1});
            }
        }
        return target;
    }
};